
"""输入：head = [1,2,3,4,5]
输出：[3,4,5]
解释：链表只有一个中间结点，值为 3 。

输入：head = [1,2,3,4,5,6]
输出：[4,5,6]
解释：该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。
"""
from typing import Optional


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        """这道题要求指向链表中间！
        快慢指针法，快指针速度是慢指针两倍，当快指针指向链表末尾，慢指针指向链表中间"""
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        # 返回中间节点后面的新链表头节点
        return slow
    
    def middleNode_1(self, head: Optional[ListNode]) -> Optional[ListNode]:
        A = [head]
        while A[-1].next:  # 当链表末尾节点的下一个不为空时，遍历
            A.append(A[-1].next)
        return A[len(A) // 2]

    def middleNode_2(self, head: Optional[ListNode]) -> Optional[ListNode]:
        counter = 0
        copy = head
        while copy:
            copy = copy.next
            counter += 1

        if counter % 2 == 0:
            counter = counter / 2 + 1
        else:
            counter = (counter + 1) / 2

        for i in range(int(counter) - 1):
            head = head.next

        return head


if __name__ == "__main__":
    # 创建一个单链表
    head = ListNode(1)
    head.next = ListNode(2)
    head.next.next = ListNode(3)
    head.next.next.next = ListNode(4)
    head.next.next.next.next = ListNode(5)

    solution = Solution()
    middle_node = solution.middleNode(head)
    # 打印新链表的值
    current = middle_node
    # while current:
    #     print(current.val, end=" -> ")
    #     current = current.next
    result = []
    while current:
        result.append(current.val)
        current = current.next
    print(result)